home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Kernel / Em / set.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-08-17  |  7.4 KB  |  353 lines
  1.  
  2.  
  3. /* Copyright 1986 Norm Hutchinson and Eric Jul.  May not be used for any   *
  4.  * purpose without written permission from the author.               */
  5.  
  6. /*
  7.  * Sets are sets of integers.
  8.  */
  9.  
  10. #include "Kernel/h/assert.h"
  11. #include "Kernel/h/system.h"
  12. #include "Kernel/h/set.h"
  13.  
  14. #define INITIALSIZE 8
  15.  
  16. #define SETHASH(key, set) ((((key) << 1) ^ ((key) >> 6)) & set->maxIndex)
  17. static void CheckOutSetHashTable();
  18.  
  19. #define MAXSETSTANDBY 20
  20. int              nextFreeSet = 0;
  21. Set              standbySets[MAXSETSTANDBY];
  22.  
  23. Set Set_Create()
  24. {
  25.   register Set              m;
  26.   register SETElemPtr       elem, stopelem;
  27.   register int              myNil = NIL;
  28.   
  29.   if (nextFreeSet > 0) {
  30.     /* Grab one from standby stack */
  31.     m           = standbySets[--nextFreeSet];
  32.     return m;
  33.   }
  34.  
  35.   m = (Set) malloc(sizeof(SetRecord));
  36.   m->maxIndex = INITIALSIZE - 1;
  37.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  38.   m->count = 0;
  39.   m->table = (SETElemPtr) malloc(INITIALSIZE * sizeof(SETElem));
  40.   elem = &m->table[0];
  41.   stopelem = &m->table[INITIALSIZE];
  42.   do {
  43.     elem->key = myNil;
  44.     elem++;
  45.   } while (elem != stopelem);
  46.   
  47. #ifdef DEBUGSET
  48.       CheckOutSetHashTable(m);
  49. #endif DEBUGSET
  50.   return(m);
  51. }
  52.  
  53. Set Set_CreateSized(fCount)
  54. int fCount;
  55. {
  56.   register int i;
  57.   register Set m;
  58.   register SETElemPtr entryPtr;
  59.   register int              myNil = NIL;
  60.  
  61.   assert(fCount > 0);
  62.   m = (Set) malloc(sizeof(SetRecord));
  63.   /* Make i the first power of two greater than fCount */
  64.   for (i = 1; i <= fCount; i += i);
  65.   i--;
  66.   m->maxIndex     = i;
  67.   m->maxCount     = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  68.   m->count     = 0;
  69.   m->table     = (SETElemPtr) malloc((unsigned)((i+1) * sizeof(SETElem)));
  70.   entryPtr      = &m->table[i+1];
  71.   do {
  72.     (--entryPtr)->key = myNil;
  73.   } while (--i >= 0);
  74.   
  75. # ifdef lint
  76.   CheckOutSetHashTable(m);
  77. #endif  
  78. #ifdef DEBUGSET
  79.   CheckOutSetHashTable(m);
  80. #endif DEBUGSET
  81.   return(m);
  82. }
  83.  
  84. void Set_Destroy(m)
  85. register Set m;
  86. {
  87.   if (m == (Set) NULL) return;
  88.   if ((nextFreeSet < MAXSETSTANDBY)
  89.     && (m->maxIndex == INITIALSIZE - 1)
  90.   ) {
  91.       if (m->count != 0) {
  92.           register int i;
  93.           register SETElemPtr entryPtr;
  94.           register int myNil = NIL;
  95.  
  96.       /* Reinitialize it */
  97.       i = m->maxIndex;
  98.       entryPtr  = &m->table[i+1];
  99.           do {
  100.             /* Optimized for portable CC for VAX */
  101.         (--entryPtr)->key = myNil;
  102.       } while (--i >= 0);
  103.           m->count = 0;
  104.       }
  105.       
  106.       /* Nice set, recycle it */
  107.       standbySets[nextFreeSet++] = m;
  108. #ifdef DEBUGMAP
  109.       CheckOutSetHashTable(m);
  110. #endif DEBUGMAP
  111.       return;
  112.   }
  113. #ifdef DEBUGSET
  114.   CheckOutSetHashTable(m);
  115. #endif DEBUGSET
  116.   free((char *)m->table);
  117.   free((char *)m);
  118. }
  119.  
  120. static void ExpandSetHashTable(m)
  121. register Set m;
  122. {
  123.   register SETElem *nh, *oe, *ne;
  124.   register int oldHashTableSize = m->maxIndex + 1, i;
  125.   register int key;
  126.   int index;
  127.  
  128.   m->maxIndex = oldHashTableSize * 2 - 1;
  129.   m->maxCount = m->maxIndex - (m->maxIndex >> 2);
  130.   nh = (SETElemPtr) malloc((unsigned)(oldHashTableSize * 2 * sizeof(SETElem)));
  131.   for (i = 0; i <= m->maxIndex; i++) nh[i].key = NIL;
  132.   for (i = 0; i < oldHashTableSize; i++) {
  133.     oe = &m->table[i];
  134.     key = oe->key;
  135.     if (key == NIL) continue;
  136.     index = SETHASH(key, m);
  137.     while (1) {
  138.       ne = &nh[index];
  139.       if (ne->key == NIL) {
  140.     ne->key = oe->key;
  141.     break;
  142.       } else {
  143.     assert(ne->key !=key);
  144.     index++;
  145.     if (index > m->maxIndex) index = 0;
  146.       }
  147.     }
  148.   }
  149.   free((char *)m->table);
  150.   m->table = nh;
  151. #ifdef DEBUGSET
  152.   CheckOutSetHashTable(m);
  153. #endif DEBUGSET
  154. }
  155.  
  156. int Set_Lookup(m, key)
  157. register Set m;
  158. register int key;
  159. {
  160.   register int index = SETHASH(key, m);
  161.   register SETElemPtr e;
  162.   register limit    = m->maxIndex;
  163.   
  164. #ifdef DEBUGSET
  165.   CheckOutSetHashTable(m);
  166. #endif DEBUGSET
  167.   while (1) {
  168.     e = &m->table[index];
  169.     if (e->key == NIL) {        /* we did not find it */
  170.       return (NIL);
  171.     } else if (e->key == key) {
  172.       return (e->key);
  173.     }
  174.     if (++index > limit) index = 0;
  175.   }
  176. }
  177.  
  178. int Set_Member(m, key)
  179. register Set m;
  180. register int key;
  181. {
  182.   register int index = SETHASH(key, m);
  183.   register SETElemPtr e;
  184.   register int myNil = NIL;
  185.  
  186. #ifdef DEBUGSET
  187.   CheckOutSetHashTable(m);
  188. #endif DEBUGSET
  189.   e = &m->table[index];
  190.   while (1) {
  191.     if (e->key == myNil) {        /* we did not find it */
  192.       return (0);
  193.     } else if (e->key == key) {
  194.       return (1);
  195.     }
  196.     e++;
  197.     if (++index > m->maxIndex) {
  198.     index = 0;
  199.         e = &m->table[0];
  200.     }
  201.   }
  202. }
  203.  
  204. void Set_Delete(m, key)
  205. register Set m;
  206. register int key;
  207. /* Remove the entry, if it is there */
  208. {
  209.   register int index = SETHASH(key, m);
  210.   register SETElemPtr e;
  211.  
  212.   while (1) {
  213.     e = &m->table[index];
  214.     if (e->key == NIL) {        /* we did not find it */
  215. #ifdef DEBUGSET
  216.       CheckOutSetHashTable(m);
  217. #endif DEBUGSET
  218.       return;
  219.     }
  220.     if (e->key == key) {
  221.       /* Found it, now remove it */
  222.       m->count--;
  223.       e->key = NIL;
  224.       while (1) {
  225.     /* rehash until we reach nil again */
  226.     if (++index > m->maxIndex) index = 0;
  227.     e = & m->table[index];
  228.     key = e->key;
  229.     if (key == NIL) {
  230. #ifdef DEBUGSET
  231.         CheckOutSetHashTable(m);
  232. #endif DEBUGSET
  233.         return;
  234.     }
  235.     /* rehashing is done by removing then reinserting */
  236.     e->key = NIL;
  237.     m->count--;
  238.     Set_Insert(m, key);
  239.       }
  240.     }
  241.     if (++index > m->maxIndex) index = 0;
  242.   }
  243. }
  244.  
  245. void Set_Insert(m, key)
  246. register Set m;
  247. register int key;
  248. {
  249.   register int index;
  250.   register SETElemPtr e;
  251.   assert(key != NIL);
  252.   if (m->count >= m->maxCount) ExpandSetHashTable(m);
  253.   index = SETHASH(key, m);
  254.   while (1) {
  255.     e = &m->table[index];
  256.     if (e->key == NIL) {        /* put it here */
  257.       e->key = key;
  258.       m->count++;
  259. #ifdef DEBUGSET
  260.       CheckOutSetHashTable(m);
  261. #endif DEBUGSET
  262.       return;
  263.     } else if (e->key == key) {
  264.       /* Already in set */
  265. #ifdef DEBUGSET
  266.       CheckOutSetHashTable(m);
  267. #endif DEBUGSET
  268.       return;
  269.     }
  270.     if (++index > m->maxIndex) index = 0;
  271.   }
  272. }
  273.  
  274. int Set_FindNext(m, startIndex, keyPtr)
  275. register Set m;
  276. int *startIndex;
  277. int *keyPtr;
  278. {
  279.   register int i;
  280.   register SETElemPtr e;
  281.   for (i = *startIndex; i <= m->maxIndex; i++) {
  282.     e = &m->table[i];
  283.     if (e->key != NIL) {
  284.       *keyPtr = e->key;
  285.       *startIndex = i + 1;
  286.       return(1);
  287.     }
  288.   }
  289.   *keyPtr = NIL;
  290.   *startIndex = -1;
  291.   return(0);
  292. }
  293.  
  294. void Set_Print(m)
  295. register Set m;
  296. {
  297.     int key, index;
  298.     printf(
  299.     "\nDump of set @ 0x%05x, %d entr%s, current max %d\nIndex\tKey\n",
  300.     m, m->count, m->count == 1 ? "y" : "ies",  m->maxCount);
  301.     for (index = 0; index <= m->maxIndex; index++) {
  302.     key = m->table[index].key;
  303.     printf("%3d\t0x%08.8x\n", index, key);
  304.     }
  305. }
  306.  
  307. static void CheckOutSetHashTable(m)
  308. register Set m;
  309. {
  310.   register int i;
  311.   register SETElemPtr realElement, e;
  312.   register int index, firstIndex, count;
  313.   count = 0;
  314.  
  315.   for (i = 0; i <= m->maxIndex; i++) {
  316.     realElement = &m->table[i];
  317.     if (realElement->key != NIL) {
  318.       count++;
  319.       index = SETHASH(realElement->key, m);
  320.       firstIndex = index;
  321.       while (1) {
  322.     e = &m->table[index];
  323.     if (e->key == NIL) {        /* we did not find it */
  324.       break;
  325.     } else if (e->key == realElement->key) {
  326.       break;
  327.     } else {
  328.       index++;
  329.       if (index > m->maxIndex) index = 0;
  330.       if (index == firstIndex) {
  331.         index = -1;
  332.         break;
  333.       }
  334.     }
  335.       }
  336.       
  337.       if (index == -1 || e->key != realElement->key) {
  338.       printf(
  339.         "Set problem: Key 0x%x, rightIndex %d, realIndex %d\n",
  340.         realElement->key, firstIndex, index);
  341.       Set_Print(m);
  342.       }
  343.     }
  344.   }  
  345.   if (count != m->count) {
  346.     printf(
  347.       "Set problem: Should have %d entries, but found %d.\n", m->count,
  348.       count);
  349.     Set_Print(m);
  350.   }
  351. }
  352.  
  353.